package leetcode_100;

/**
 *@author 周杨
 *RemoveDuplicatesFromSortedListII_82 删除一个有序链表中重复的节点 不保存这个值
 *describe: 记录当前遍历的值 来判断此处节点是否加入链表 加入链表还有一个条件 此节点要么没有下一个节点 要么下一个节点的值不等于当前节点的值
 *          AC 100%
 *2018年5月15日 下午1:52:42
 */
public class RemoveDuplicatesFromSortedListII_82 {
	static class ListNode{
		int val;
		ListNode next;
		ListNode(int x){val = x;};
	}
	public static void main(String[] args) {
		RemoveDuplicatesFromSortedListII_82 test=new RemoveDuplicatesFromSortedListII_82();
		ListNode a=new ListNode(1);
		ListNode b=new ListNode(1);
		ListNode c=new ListNode(1);
		ListNode d=new ListNode(2);
		ListNode e=new ListNode(3);
		ListNode f=new ListNode(5);
		ListNode g=new ListNode(5);
		
		a.next=b;
		b.next=c;
		c.next=d;
		d.next=e;
		e.next=f;
		f.next=g;
		ListNode res=test.deleteDuplicates(a);

	}
	
	public ListNode deleteDuplicates(ListNode head) {
		if(head==null)
			return null;
		if(head.next==null)
			return head;
		int nowVal=head.val;
		ListNode newHead=null,run=head.next,nowNode=null;
		if(head.next.val!=head.val) {//此处先判断head是否废弃
			newHead=head;
			nowNode=head;
		}
		while(run!=null) {
			if(run.val!=nowVal) {//加入链表的第一个条件
				nowVal=run.val;
				if(run.next==null||run.next.val!=nowVal) {//可以加入链表
					if(newHead==null) {//是否还没有确定返回节点 也就是之前的节点都是废弃节点
						newHead=run;
						nowNode=run;
					}
					else {//已经有了返回节点 更新尾部连接的下一个节点
						nowNode.next=run;
						nowNode=run;
					}
				}
				
			}
			run=run.next;
		}
		if(nowNode!=null)//将尾部删除
			nowNode.next=null;
		return newHead;
	}

}
